package 力扣_算法题综合.自己不会但觉得高频;

import java.util.ArrayDeque;


/**
 * @author zx
 * @create 2023-01-05 21:33
 * 代码随想录解法,去年这种题做挺多的,但是这种解法是最全面的
 * 之前投机取巧的解法过不了
 */
public class 反转字符串中的单词_151 {
    /**题目要求：空间复杂度O(1)
     * 1.去除首尾以及中间多余空格
     * 2.反转整个字符串
     * 3.反转各个单词
     * eg：源字符串为：  "the    sky is blue "
     *   1.移除多余空格: "the sky is blue"
     *   2.字符串反转：  "eulb si yks eht"
     *   3.单词反转：    "blue is sky the"
     */
    public String reverseWords(String s) {
        StringBuilder res = removeSpace(s);
        reverseString(res, 0, res.length() - 1);
        reverseEveryWord(res);
        return res.toString();
    }
    /**
     * 去除首尾以及中间多余空格
     */
    private StringBuilder removeSpace(String s) {
        int left = 0, right = s.length() - 1;
        while (s.charAt(left) == ' ') {
            left++;
        }
        while (s.charAt(right) == ' ') {
            right--;
        }
        StringBuilder res = new StringBuilder();
        while (left <= right) {
            char c = s.charAt(left);
            if (c != ' ') {
                res.append(c);
            } else if (c == ' ' && res.charAt(res.length() - 1) != ' ') {
                res.append(c);
            }
            left++;
        }
        return res;
    }

    /**
     * 反转字符串指定区间[start, end]的字符
     */
    public void reverseString(StringBuilder sb, int left, int right) {
        while (left < right) {
            char temp = sb.charAt(left);
            sb.setCharAt(left, sb.charAt(right));
            sb.setCharAt(right, temp);
            left++;
            right--;
        }
    }

    /**
     * 反转各个单词
     */
    private void reverseEveryWord(StringBuilder s) {
        int left = 0;
        int right = 1;
        while (left < s.length()) {
            while (right < s.length() && s.charAt(right) != ' ') {
                right++;
            }
            reverseString(s, left, right - 1);
            left = right + 1;
            right = left + 1;
        }
    }

    /**
     * @return 我当时的思路,现在看着代码挺简洁的
     */
    public String reverseWords2(String s) {
        String[] str = s.split(" ");
        ArrayDeque stack = new ArrayDeque();
        for(int i = 0;i < str.length;i++){
            stack.push(str[i]);
        }
        String res = "";
        int count = 0;
        int size = stack.size();
        while(!stack.isEmpty()){
            String c = (String)stack.pop();
            if(c != ""){
                res = res + c + " ";
            }
        }
        //trim():去除字符串两端空格
        return res.trim();
    }
}
